package h0908;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LeastRencentlyUsed {
    static class LRUCache {
        static class Node {
            int val;
            int key;
            Node prev;
            Node next;

            public Node(int key, int val) {
                this.val = val;
                this.key = key;
            }
        }

        private Map<Integer, Node> map;
        private final int capacity;
        private final Node head, tail;

        public LRUCache(int capacity) {
            map = new HashMap<>();
            this.capacity = capacity;
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node node = map.get(key);
            moveToHead(node);
            return node.val;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                //如果包含当前key
                Node node = map.get(key);
                node.val = value;//更新数据
                //移动到头部
                moveToHead(node);
            } else {
                if (map.size() >= capacity) {
                    Node node = removeTail();
                    map.remove(node.key);
                }
                Node newNode = new Node(key, value);
                map.put(key, newNode);
                addToHead(newNode);
            }
        }

        private void addToHead(Node node) {
            node.next = head.next;
            head.next.prev = node;
            node.prev = head;
            head.next = node;
        }

        private void moveToHead(Node node) {
            removeNode(node);
            addToHead(node);
        }

        private void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public Node removeTail() {
            Node res = tail.prev;
            removeNode(res);
            return res;
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(2, 6);
        cache.get(2);
        cache.get(1);
        cache.put(1, 5);
        cache.put(1, 2);
        cache.get(1);
        System.out.println(cache.get(2));
    }
}
